from typing import List


class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        def is_valid(l):
            if len(l) < 3:
                return False

            for i in range(len(l) - 2):
                if l[i] + l[i + 1] != l[i + 2]:
                    return False
            return True

        def check(l):
            if not 0 <= l[-1] < 2 ** 31 - 1:
                return False
            if len(l) < 4:
                return True
            return l[-4] + l[-3] == l[-2]

        def backtrack(l, start):
            if not check(l):
                return
            if start >= len(S):
                print(l)
                if is_valid(l):
                    return l
                return
            if res := backtrack([*l, int(S[start])], start + 1):
                return res

            if l[-1] != 0:
                if res := backtrack([*l[:-1], l[-1] * 10 + int(S[start])], start + 1):
                    return res

        return backtrack([int(S[0])], 1) or []


if __name__ == "__main__":
    S = "123456579"
    # S = "0123"
    # S = "11011"
    # S = "1101111"
    # S = "539834657215398346785398346991079669377161950407626991734534318677529701785098211336528511"
    res = Solution().splitIntoFibonacci(S)
    print(res)

